﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinaryTree
{
    public class BTreeWithLinks:ITree
    {
        Link root = new Link();

        public BTreeWithLinks() { }
        public BTreeWithLinks(Link _root)
        {
            root = _root;
        }
        public void AddNode(int val)
        {
            addNode(root, val);
        }
        private void addNode(Link _root, int val)
        {
            if (_root.link==null)
            {
                _root.link = new Node(val);
            }
            else
            {
                if (val < _root.link.value)
                {
                    addNode(_root.link.left, val);
                }
                else
                {
                    addNode(_root.link.right, val);
                }
            }
        }
        void inorder(Link _root, ref List<int> rez)
        {
            if (_root.link != null)
            {

                inorder(_root.link.left, ref rez);
                if (_root != null)
                {
                    rez.Add(_root.link.value);
                }
                inorder(_root.link.right, ref rez);
            }
        }
        public List<int> SortValuePrint()
        {
            List<int> rez = new List<int>();
            inorder(root, ref rez);
            return rez;
        }
        public int Height()
        {
            return Height(root);
        }
        private int Height(Link _root)
        {
            int h = 0;
            if (_root.link != null)
            {
                h = Math.Max(Height(_root.link.right), Height(_root.link.left)) + 1;
            }
            return h;
        }
        private int AmountOfNodesOnILevel(Link _root, int i)
        {
            int amount = 0;
            if (i > 0)
            {
                if (_root.link == null)
                {
                    amount = 0;
                }
                else
                {
                    if (i == 1)
                    {
                        amount = 1;
                    }
                    else
                    {
                        amount = AmountOfNodesOnILevel(_root.link.left, i - 1) + AmountOfNodesOnILevel(_root.link.right, i - 1);
                    }
                }
            }
            return amount;
        }
        public int Width()
        {
            int w = 0;
            int[] width = new int[Height(root)];
            for (int i = 0; i < width.Length; i++)
            {
                width[i] = AmountOfNodesOnILevel(root, i + 1);
            }
            if (width.Length != 0)
            {
                w = width[0];
            }
            for (int i = 1; i < width.Length; i++)
            {
                if (w < width[i])
                {
                    w = width[i];
                }
            }
            return w;
        }
        public int AmountOfLeaves()
        {
            return AmountOfLeaves(root);
        }
        private int AmountOfLeaves(Link _root)
        {
            int l = 0;
            if (_root.link == null)
            {
                l = 0;
            }
            else
            {
                if (_root.link.left.link == null && _root.link.right.link == null)
                {
                    l = 1;
                }
                else
                {
                    l = AmountOfLeaves(_root.link.left) + AmountOfLeaves(_root.link.right);
                }
            }
            return l;
        }
        public int AmountOfNodes()
        {
            int r = 0;
            AmountOfNodes(root, ref r);
            return r;
        }
        private void AmountOfNodes(Link _root, ref int r)
        {
            if (_root.link != null)
            {
                if (_root.link.left.link != null || _root.link.right.link != null)
                {
                    r++;
                    AmountOfNodes(_root.link.left, ref r);
                    AmountOfNodes(_root.link.right, ref r);
                }
            }
        }
        public int TotalAmountOfNodes()
        {
            int r = 0;
            AmountOfNodes(root, ref r);
            return r + AmountOfLeaves();
        }
        public void Revers()
        {
            Revers(root);
        }
        private void Revers(Link _root)
        {
            Link temp = null;
            if (_root.link != null)
            {
                temp = _root.link.right;
                _root.link.right = _root.link.left;
                _root.link.left = temp;
                Revers(_root.link.left);
                Revers(_root.link.right);
            }
        }
        public Link Search(int val)
        {
            return Search(root, val);
        }
        private Link Search(Link _root,int val)
        {
            Link node=null;
            if (_root.link != null)
            {
                if (_root.link.value == val)
                {
                    node = _root;
                }
                else
                {
                    if (val < _root.link.value)
                    {
                        node=Search(_root.link.left, val);
                    }
                    else
                    {
                        node=Search(_root.link.right, val);
                    }

                }
            }
            return node;
        }

        private void setNull(Link _root, int val)
        {
            if (_root.link != null)
            {
                if (_root.link.value == val)
                {
                    _root.link=null;
                }
                else
                {
                    if (val < _root.link.value)
                    {
                        setNull( _root.link.left, val);
                    }
                    else
                    {
                        setNull(_root.link.right, val);
                    }

                }
            }
        }
        private void addTree(Link _root)
        {
            if (_root.link != null)
            {
                addNode(root, _root.link.value);
                if (_root.link.left.link != null)
                {
                    addTree(_root.link.left);
                }
                if (_root.link.right.link != null)
                {
                    addTree(_root.link.right);
                }
            }
        }
        public void DelNode(int val)
        {
            BTreeWithLinks node = new BTreeWithLinks();
            node.addTree(Search(val));
            //Link node = Search(val);
            if (node.root.link != null)
            {
                setNull(root, val);
                if (node.root.link.left.link == null)
                {
                    addTree(node.root.link.right);
                }
                else
                {
                    if (node.root.link.right.link == null)
                    {
                        addTree(node.root.link.left);
                    }
                    else
                    {
                        addTree(node.root.link.left);
                        addTree(node.root.link.right);
                    }
                }
            }
        }
    }
}
